package com.warningrc.demo;

import java.util.ArrayList;
import java.util.PriorityQueue;


public class DFS_7 {
    // 定义图节点类
    static class Node {
        // 节点的值
        int value;
        // 存储该节点的邻接节点列表
        ArrayList<Node> neighbors;

        Node(int value) {
            this.value = value;
            this.neighbors = new ArrayList<>();
        }
    }

    // 定义带权边类，实现Comparable接口用于比较边的权值大小
    static class WeightedEdge implements Comparable<WeightedEdge> {
        int source; // 边的源节点
        int destination; // 边的目标节点
        int weight; // 边的权值

        // 带权边类的构造函数
        public WeightedEdge(int source, int destination, int weight) {
            this.source = source;
            this.destination = destination;
            this.weight = weight;
        }

        // 实现compareTo方法，用于在优先级队列中比较边的权值
        @Override
        public int compareTo(WeightedEdge other) {
            return Integer.compare(this.weight, other.weight);
        }
    }

    // 定义带权节点类
    static class WeightedNode {
        int value; // 节点的值
        ArrayList<WeightedNode> neighbors; // 存储该节点的邻接节点列表
        ArrayList<Integer> weights; // 存储与邻接节点相连边的权值列表

        // 带权节点类的构造函数
        public WeightedNode(int value) {
            this.value = value;
            this.neighbors = new ArrayList<>();
            this.weights = new ArrayList<>();
        }
    }

    // 使用DFS辅助Prim算法构建最小生成树的方法，接受起始节点作为参数
    public static ArrayList<WeightedEdge> primWithDFS(WeightedNode start) {
        ArrayList<WeightedEdge> minimumSpanningTree = new ArrayList<>(); // 存储最小生成树的边
        boolean[] inMST = new boolean[100]; // 标记节点是否在最小生成树中，假设图中最多有100个节点，根据实际情况调整大小
        // 将起始节点加入最小生成树
        inMST[start.value] = true;

        // 循环直到所有节点都加入最小生成树
        while (true) {
            WeightedEdge minEdge = null;
            // 遍历已在最小生成树中的节点
            for (int i = 0; i < inMST.length; i++) {
                if (inMST[i]) {
                    WeightedNode currentNode = findNodeByValue(i, start); // 找到当前节点
                    if (currentNode != null) {
                        // 使用DFS找到当前节点的最小权值邻接边
                        WeightedEdge edge = findMinWeightEdgeWithDFS(currentNode, inMST);
                        if (edge != null && (minEdge == null || edge.weight < minEdge.weight)) {
                            minEdge = edge;
                        }
                    }
                }
            }
            // 如果没有找到可以加入最小生成树的边，说明所有节点都已加入，结束循环
            if (minEdge == null) {
                break;
            }
            // 将找到的最小权值边加入最小生成树
            minimumSpanningTree.add(minEdge);
            // 将新加入边的目标节点标记为已在最小生成树中
            inMST[minEdge.destination] = true;
        }
        return minimumSpanningTree;
    }

    // 根据节点值在图中找到对应的节点（通过递归遍历）
    private static WeightedNode findNodeByValue(int value, WeightedNode start) {
        if (start.value == value) {
            return start;
        }
        for (WeightedNode neighbor : start.neighbors) {
            WeightedNode foundNode = findNodeByValue(value, neighbor);
            if (foundNode != null) {
                return foundNode;
            }
        }
        return null;
    }

    // 使用DFS找到节点的最小权值邻接边（排除已在最小生成树中的节点）
    private static WeightedEdge findMinWeightEdgeWithDFS(WeightedNode node, boolean[] inMST) {
        PriorityQueue<WeightedEdge> minHeap = new PriorityQueue<>(); // 用于存储邻接边，自动根据权值排序（最小堆）
        boolean[] visited = new boolean[100]; // 标记节点是否已被访问，假设图中最多有100个节点，根据实际情况调整大小
        dfsForMinEdge(node, inMST, minHeap, visited); // 调用辅助的DFS方法
        return minHeap.poll(); // 取出最小权值边
    }

    // 辅助的DFS方法，用于找到最小权值邻接边并加入最小堆
    private static void dfsForMinEdge(WeightedNode node, boolean[] inMST, PriorityQueue<WeightedEdge> minHeap, boolean[] visited) {
        visited[node.value] = true; // 标记当前节点已被访问
        // 遍历当前节点的邻接节点和对应的权值
        for (int i = 0; i < node.neighbors.size(); i++) {
            WeightedNode neighbor = node.neighbors.get(i);
            int weight = node.weights.get(i);
            // 如果邻接节点未被访问且不在最小生成树中
            if (!visited[neighbor.value] && !inMST[neighbor.value]) {
                minHeap.add(new WeightedEdge(node.value, neighbor.value, weight)); // 将边加入最小堆
            }
        }
        // 递归遍历未访问的邻接节点
        for (WeightedNode neighbor : node.neighbors) {
            if (!visited[neighbor.value]) {
                dfsForMinEdge(neighbor, inMST, minHeap, visited);
            }
        }
    }
}